package com.bichengcao.googlecodejam.qualification2008;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class SavingTheUniverse {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/qualification2008/A-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/qualification2008/SavingTheUniverse.out", outputs);
	}

	static class Input {

		int S;
		int Q;
		String[] searchEngines;
		String[] queries;
	}

	static class Output {

		int switches;
	}
	
	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			input.S = Integer.parseInt(in.readLine());
			input.searchEngines = new String[input.S];
			for (int j = 0; j < input.S; j++) {
				input.searchEngines[j] = in.readLine();
			}
			input.Q = Integer.parseInt(in.readLine());
			input.queries = new String[input.Q];
			for (int j = 0; j < input.Q; j++) {
				input.queries[j] = in.readLine();
			}
		}

		in.close();
		return array;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		int index = 0;
		while (index < input.queries.length) {
			int[] startIndexes = new int[input.searchEngines.length];
			for (int i = 0; i < input.searchEngines.length; i++) {
				startIndexes[i] = input.queries.length;
				for (int j = index; j < input.queries.length; j++) {
					if (input.queries[j].equals(input.searchEngines[i])) {
						startIndexes[i] = j;
						break;
					}
				}
			}
			
			/*
			 * Find the maximum start index of all search engines, then we can use this search engine
			 * for queries from index to this maximum start index - 1.
			 */
			int maxIndex = 0;
			for (int i = 0; i < input.searchEngines.length; i++) {
				if (startIndexes[i] > maxIndex) {
					maxIndex = startIndexes[i];
				}
			}
			
			if (maxIndex == input.queries.length) {
				// Some safe search engine found for all left queries
				return output;
			} else {
				output.switches++;
				index = maxIndex;
			}
		}

		return output;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ": " + outputs[i].switches);
		}
		out.close();
	}

}
